๋ฌธ์
์ฌํ์์ ์์ฅ ๊ตฌ์ฌํ์ ์ง๋ ๋ช ๋ ๊ฐ ๊ฒ๋ฆฌ๋งจ๋๋ง์ ํตํด์ ์์ ์ ๋น์๊ฒ ์ ๋ฆฌํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ค. ๊ฒฌ์ ํ ๊ถ๋ ฅ์ด ์์ด์ง ๊ตฌ์ฌํ์ ๊ถ๋ ฅ์ ๋งค์ฐ ๋ถ๋นํ๊ฒ ํ์ฌํ๊ณ , ์ฌ์ง์ด๋ ์์ ์ด๋ฆ๋ ์ฌํ์๋ก ๋ณ๊ฒฝํ๋ค. ์ด๋ฒ ์ ๊ฑฐ์์๋ ์ต๋ํ ๊ณตํํ๊ฒ ์ ๊ฑฐ๊ตฌ๋ฅผ ํ์ ํ๋ ค๊ณ ํ๋ค.
์ฌํ์๋ ํฌ๊ธฐ๊ฐ NรN์ธ ๊ฒฉ์๋ก ๋ํ๋ผ ์ ์๋ค. ๊ฒฉ์์ ๊ฐ ์นธ์ ๊ตฌ์ญ์ ์๋ฏธํ๊ณ , rํ c์ด์ ์๋ ๊ตฌ์ญ์ (r, c)๋ก ๋ํ๋ผ ์ ์๋ค. ๊ตฌ์ญ์ ๋ค์ฏ ๊ฐ์ ์ ๊ฑฐ๊ตฌ๋ก ๋๋ ์ผ ํ๊ณ , ๊ฐ ๊ตฌ์ญ์ ๋ค์ฏ ์ ๊ฑฐ๊ตฌ ์ค ํ๋์ ํฌํจ๋์ด์ผ ํ๋ค. ์ ๊ฑฐ๊ตฌ๋ ๊ตฌ์ญ์ ์ ์ด๋ ํ๋ ํฌํจํด์ผ ํ๊ณ , ํ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋์ด ์๋ ๊ตฌ์ญ์ ๋ชจ๋ ์ฐ๊ฒฐ๋์ด ์์ด์ผ ํ๋ค. ๊ตฌ์ญ A์์ ์ธ์ ํ ๊ตฌ์ญ์ ํตํด์ ๊ตฌ์ญ B๋ก ๊ฐ ์ ์์ ๋, ๋ ๊ตฌ์ญ์ ์ฐ๊ฒฐ๋์ด ์๋ค๊ณ ํ๋ค. ์ค๊ฐ์ ํตํ๋ ์ธ์ ํ ๊ตฌ์ญ์ 0๊ฐ ์ด์์ด์ด์ผ ํ๊ณ , ๋ชจ๋ ๊ฐ์ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ๊ตฌ์ญ์ด์ด์ผ ํ๋ค.
์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋๋ ๋ฐฉ๋ฒ์ ๋ค์๊ณผ ๊ฐ๋ค.
- ๊ธฐ์ค์ (x, y)์ ๊ฒฝ๊ณ์ ๊ธธ์ด d1, d2๋ฅผ ์ ํ๋ค. (d1, d2 โฅ 1, 1 โค x < x+d1+d2 โค N, 1 โค y-d1 < y < y+d2 โค N)
-
๋ค์ ์นธ์ ๊ฒฝ๊ณ์ ์ด๋ค.
- (x, y), (x+1, y-1), ..., (x+d1, y-d1)
- (x, y), (x+1, y+1), ..., (x+d2, y+d2)
- (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
- (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
- ๊ฒฝ๊ณ์ ๊ณผ ๊ฒฝ๊ณ์ ์ ์์ ํฌํจ๋์ด์๋ ๊ณณ์ 5๋ฒ ์ ๊ฑฐ๊ตฌ์ด๋ค.
-
5๋ฒ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋์ง ์์ ๊ตฌ์ญ (r, c)์ ์ ๊ฑฐ๊ตฌ ๋ฒํธ๋ ๋ค์ ๊ธฐ์ค์ ๋ฐ๋ฅธ๋ค.
- 1๋ฒ ์ ๊ฑฐ๊ตฌ: 1 โค r < x+d1, 1 โค c โค y
- 2๋ฒ ์ ๊ฑฐ๊ตฌ: 1 โค r โค x+d2, y < c โค N
- 3๋ฒ ์ ๊ฑฐ๊ตฌ: x+d1 โค r โค N, 1 โค c < y-d1+d2
- 4๋ฒ ์ ๊ฑฐ๊ตฌ: x+d2 < r โค N, y-d1+d2 โค c โค N
์๋๋ ํฌ๊ธฐ๊ฐ 7ร7์ธ ์ฌํ์๋ฅผ ๋ค์ฏ ๊ฐ์ ์ ๊ฑฐ๊ตฌ๋ก ๋๋ ๋ฐฉ๋ฒ์ ์์์ด๋ค.
๊ตฌ์ญ (r, c)์ ์ธ๊ตฌ๋ A[r][c]์ด๊ณ , ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ๋ ์ ๊ฑฐ๊ตฌ์ ํฌํจ๋ ๊ตฌ์ญ์ ์ธ๊ตฌ๋ฅผ ๋ชจ๋ ํฉํ ๊ฐ์ด๋ค. ์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋๋ ๋ฐฉ๋ฒ ์ค์์, ์ธ๊ตฌ๊ฐ ๊ฐ์ฅ ๋ง์ ์ ๊ฑฐ๊ตฌ์ ๊ฐ์ฅ ์ ์ ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ ์ฐจ์ด์ ์ต์๊ฐ์ ๊ตฌํด๋ณด์.
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ฌํ์์ ํฌ๊ธฐ N์ด ์ฃผ์ด์ง๋ค.
- ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์ N๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ง๋ค. rํ c์ด์ ์ ์๋ A[r][c]๋ฅผ ์๋ฏธํ๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ ์ธ๊ตฌ๊ฐ ๊ฐ์ฅ ๋ง์ ์ ๊ฑฐ๊ตฌ์ ๊ฐ์ฅ ์ ์ ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ ์ฐจ์ด์ ์ต์๊ฐ์ ์ถ๋ ฅํ๋ค.
๐ Logic
class Dosi {
int N;
int minDiff = Integer.MAX_VALUE;
int[][] map;
int[][] copyMap;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
...
}
- ์ ๊ฑฐ๊ตฌ์ ์ ๋ณด๋ฅผ ๋ด๋นํ๋ ํด๋์ค์ด๋ค.
public int vote() {...}
- ์ฃผ์ด์ง ๊ธฐ์ค์ ๋ฐ๋ผ ์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋๊ณ , ์ธ๊ตฌ ์๋ฅผ ํฉ์ฐํ๋ ๋ก์ง์ ์คํํ๋ ๋ฉ์๋์ด๋ค.
private void setLine(int x, int y, int d1, int d2) {...}
- 5๋ฒ ์ ๊ฑฐ๊ตฌ์ ๊ฐ์ฅ์๋ฆฌ๋ฅผ ๊ธ๊ณ , ๋ด๋ถ ์์ญ์ ํ์ํ๋
isConnected๋ฅผ ์คํํ๋ ๋ฉ์๋์ด๋ค.
private void isConnected(int x, int y) {...}
- ์ฌ๊ท์ ์ผ๋ก 5๋ฒ ์ ๊ฑฐ๊ตฌ์ ๋ด๋ถ๋ฅผ ํ์ํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Dosi {
int N;
int minDiff = Integer.MAX_VALUE;
int[][] map;
int[][] copyMap;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
public Dosi(int N) {
this.N = N;
map = new int[N + 1][N + 1];
}
public int vote() {
for (int d1 = 1; d1 <= N; d1++) {
for (int d2 = 1; d2 <= N; d2++) {
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
if (!(x + d1 + d2 <= N && y - d1 >= 1 && y + d2 <= N)) continue;
copyMap = new int[N + 1][N + 1];
popSum1(x, y, d1);
popSum2(x, y ,d2);
popSum3(x, y, d1, d2);
popSum4(x, y, d1, d2);
setLine(x, y, d1, d2);
sum();
}
}
}
}
return minDiff;
}
private void sum() {
int max = 0;
int min = Integer.MAX_VALUE;
int[] popSum = new int[6];
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
popSum[copyMap[i][j]]+=map[i][j];
}
}
for(int i=1; i<=5; i++) {
max = Math.max(max, popSum[i]);
min = Math.min(min, popSum[i]);
}
minDiff = Math.min(minDiff, max-min);
}
private void setLine(int x, int y, int d1, int d2) {
for(int i = 0; i <= d1; i++) {
copyMap[x+i][y-i] = 5;
}
for(int i = 0; i <= d2; i++) {
copyMap[x+i][y+i] = 5;
}
for(int i = 0; i <= d2; i++) {
copyMap[x+d1+i][y-d1+i] = 5;
}
for(int i = 0; i <= d1; i++) {
copyMap[x+d2+i][y+d2-i] = 5;
}
for(int alpha = 0; alpha < d1; alpha++) {
isConnected(x+alpha+1, y-alpha);
}
for(int alpha = 0; alpha < d2; alpha++) {
isConnected(x+alpha+1, y+alpha);
}
}
private void isConnected(int x, int y) {
copyMap[x][y] = 5;
for(int i=0; i<4; i++) {
int nx = x + rangeX[i];
int ny = y + rangeY[i];
if (nx < 1 || nx > N || ny < 1 || ny > N) continue;
if (copyMap[nx][ny] != 5) isConnected(nx,ny);
}
}
private void popSum1(int x, int y, int d1) {
for (int i = 1; i < x + d1; i++) {
for (int j = 1; j <= y; j++) {
copyMap[i][j] = 1;
}
}
}
private void popSum2(int x, int y, int d2) {
for (int i = 1; i <= x + d2; i++) {
for (int j = y + 1; j <= N; j++) {
copyMap[i][j] = 2;
}
}
}
private void popSum3(int x, int y, int d1, int d2) {
for (int i = x + d1; i <= N; i++) {
for (int j = 1; j < y - d1 + d2; j++) {
copyMap[i][j] = 3;
}
}
}
private void popSum4(int x, int y, int d1, int d2) {
for (int i = x + d2 + 1; i <= N; i++) {
for (int j = y - d1 + d2; j <= N; j++) {
copyMap[i][j] = 4;
}
}
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Dosi dosi = new Dosi(N);
String[] line;
for (int i = 1; i <= N; i++) {
line = br.readLine().split(" ");
for (int j = 1; j <= N; j++) {
dosi.map[i][j] = Integer.parseInt(line[j - 1]);
}
}
System.out.println(dosi.vote());
br.close();
}
}
โ๏ธ Review
- ์ฒ์์๋ ๊ฒ๋ฆฌ๋งจ๋๋ง์ด๋ ๋น์ทํ ์ค ์์๋๋ฐ ์กฐ๊ธ์ ๋ฌ๋ผ์ ์๊ฐํด๋ณด๋๋ฐ ์๊ฐ์ด ์ข ๊ฑธ๋ ธ๋ค.
-
์ ๊ฑฐ๊ตฌ๋ฅผ ๋๋๋ ๋ก์ง์ ๊ตฌํํ๋๋ฐ ์๊ฐ์ด ๊ฑธ๋ ธ๊ณ , ๊ฒ์ํ์ ์ฐธ๊ณ ํด์ ๋๋ฆ๋๋ก ํ์ด๋ดค๋๋ฐ, ์ต์ข ์ ์ผ๋ก ์ธ๊ตฌ์๋ฅผ ํฉ์ฐํด ์ฐจ์ด์ ์ต์๋ฅผ ๊ตฌํ๋ ๋ก์ง์ด ์๊พธ ํ๋ ธ๋ค.
- ์ด์ฐจํผ ๋๋ ์ง ์ ๊ฑฐ๊ตฌ์ ์ธ๊ตฌ ์๋ฅผ ๋๋ ๋๋ง๋ค ํฉ์ฐํ๊ณ ์ ๊ฑฐ๊ตฌ๋ฅผ ๋ค ๋๋ ๋ค (์ฆ, ์ธ๊ตฌ ์ ํฉ์ฐ๊น์ง ์๋ฃ๋ ์ํ) ์ฐจ์ด๋ฅผ ๊ตฌํ๊ณ ์ด๋ฅผ ์ ๋ฐ์ดํธํ๋ ๋ฐฉ์์ ์ ํ๋ฆฌ๋์ง ๋ชจ๋ฅด๊ฒ ๋ค.
๐ ์ถ์ฒ
Baekjoon : https://www.acmicpc.net/problem/17779